from sys import argv

First = {}
Follow = {}
nterminais = {}
NT_SEM_SIGMA = {}
NULO = set([])
SIGMA = '%'
SEPARA_PROD = '@'
SEPARA_ALT = '|'
FIM_ENTRADA = '$'
COD_NT = {}
COD_T = {}
COD_R = {}
REGRA = {}

def first(cadeia, i):
    global First, nterminais, SIGMA
    if cadeia == []:
        return set([])
    N = len(cadeia) - 1
    #print i, cadeia
    simbolo = cadeia[i]
    if simbolo not in nterminais:
        if simbolo not in First: First[simbolo] = set([simbolo])
        return First[simbolo]
    else: # simbolo nao-terminal
        F = First[simbolo]
        if SIGMA in First[simbolo] and i < N:
            # print "cadeia = ", cadeia, "i=",i,"+1 < ", len(cadeia), " F, simbolo = ", F," ",simbolo
            return First[simbolo] - set([SIGMA]) | first(cadeia, i+1)
        elif i == N:
            F |= set(SIGMA)
        return F

def calcFirst():
    global First
    global nterminais
    global NULO
    while(True):
        mudou = False
        for NT in nterminais.keys():
            for cadeia in nterminais[NT]:
                # print "pre"
                F = first(cadeia, 0)
                # print "pos"
                if F - First[NT] != set([]):
                    mudou = True
                    First[NT] |= F
        if not mudou:
            return

def follow(nome, cadeia):
    global Follow, First, nterminais, SIGMA, NULO
    mudou = False
    N = len(cadeia) - 1
    for i, simbolo in enumerate(cadeia):
        if simbolo in nterminais:
            if i == N:
                F = Follow[nome]
            else:
                F = first(cadeia, i+1)
                if SIGMA in F:
                    F.remove(SIGMA)
                    F |= Follow[nome]
            if F - Follow[simbolo] != NULO:
                Follow[simbolo] |= F
                mudou = True
    return mudou

def calcFollow():
    global First
    global nterminais
    global Follow
    while(True):
        mudou = False
        for NT in nterminais.keys():
            for cadeia in nterminais[NT]:
                mudou |= follow(NT, cadeia)
        if not mudou:
            return

def code(simbolo):
    if simbolo in COD_NT:
        return str(COD_NT[simbolo])
    else:
        return str(COD_T[simbolo])
 
def isntSigma(x):
    global SIGMA
    return x != SIGMA

def leGramatica(nomeArquivo):
    global SEPARA_PROD, SEPARA_ALT, COD_NT, COD_T, COD_R, REGRA, SIGMA, NT_SEM_SIGMA
    global Follow, First
    inFile = file(inFilePath, "r")
    start = inFile.tell()
    StartGram = inFile.readline().split(SEPARA_PROD)[0].strip()
    inFile.seek(start)
    Follow[StartGram] = set([FIM_ENTRADA])
    print '============== READING ================'
    nt_i = 0
    for line in inFile:
        print "Linha da entrada: {0}".format(line)
        line = line.split(SEPARA_PROD)
        nome = line[0].strip()
        print line
        producoes = line[1]
        if nome not in First:       First[nome] = set()
        if nome not in COD_NT:
            COD_NT[nome] = nt_i
            nt_i += 1
            print "CODIGO DO NAO TERMINAL {0}: {1}".format(nome, nt_i - 1)
        if nome not in Follow:      Follow[nome] = set()
        if nome not in nterminais:  nterminais[nome] = []
        producoes = [ prod.split() for prod in producoes.split(SEPARA_ALT) ]
        nterminais[nome].extend(producoes)
    COD_T[FIM_ENTRADA] = nt_i
    COD_T[SIGMA] = nt_i + 1
    t_i = nt_i + 2 
    for NT in nterminais:
        for cadeia in nterminais[NT]:
            for simbolo in cadeia:
                if simbolo not in COD_T and simbolo not in nterminais:
                    COD_T[simbolo] = t_i
                    t_i += 1
                    print "CODIGO DO TERMINAL {0}: {1}".format(simbolo, t_i - 1)
    i_r = 0
    NT_ordered = [x[0] for x in sorted(COD_NT.items(), key=lambda x:x[1])]
    for NT in NT_ordered:
        print NT
        NT_SEM_SIGMA[NT] = []
        for cadeia in nterminais[NT]:
            regra = " ".join(map(code, cadeia))
            NT_SEM_SIGMA[NT].append(cadeia)
            if regra not in COD_R:
                REGRA[i_r] = cadeia
                COD_R[regra] = i_r
                i_r += 1
                print "CODIGO DA REGRA {0} -> {1}: {2}".format(NT, regra, i_r - 1)
        if NT_SEM_SIGMA[NT] == []:
            del(NT_SEM_SIGMA[NT])
    inFile.close()

if  __name__  ==  "__main__":
    if len(argv) != 3:
        print "uso:", argv[0],"gramatica.txt", "saida.txt"
        exit()
    inFilePath = argv[1]
    outFilePath = argv[2]
    leGramatica(inFilePath)

    print '============== FIRSTS ================'
    calcFirst()
    for k in sorted(nterminais.keys()):
        print k, First[k]

    print '============== FOLLOWS ================'
    calcFollow()
    for k in sorted(nterminais.keys()):
        print k, Follow[k]

    print '============== TABELANDO ================'
    outFile = file(outFilePath, "w")

    #M = [ []*len( COD_T ) ]*len( COD_NT )
    NUM_NT = len(COD_NT)
    outFile.write(str(NUM_NT) + "\n")
    print "ordem da saida:\nnumero de nao terminais"
    print "se numero de nao terminais = {0}, proximas {0} linhas serao os nao terminais pela ordem dos indices na tabela".format(NUM_NT)
    nt_ordered = [i[0] for i in sorted(COD_NT.items(), key=lambda x:x[1])]
    for NT in nt_ordered:
        outFile.write(NT+"\n")
    for NT in nt_ordered[:3]:
        print NT
    print "..."
    print "agora vem o numero de terminais"
    NUM_T = len(COD_T)
    outFile.write(str(NUM_T)+"\n")
    print "proximas {0} linhas serao os terminais pela ordem dos indices na tabela".format(NUM_T)
    t_ordered = [i[0] for i in sorted(COD_T.items(), key=lambda x:x[1])]
    vvv = 0
    for T in t_ordered:
        outFile.write(T+"\n")
        print vvv+len(COD_NT),T
        vvv += 1
    #for T in t_ordered[:3]:
    #    print T
    print "..."
    print "agora vem o numero derivacoes"
    NUM_R = len(COD_R)
    print "proximas {0} linhas serao as derivacoes lista de codigos dos valores da tabela".format(NUM_R)
    r_ordered = [x[0] for x in sorted(COD_R.items(), key=lambda x:x[1])]
    outFile.write(str(NUM_R)+"\n")
    for i, R in enumerate(r_ordered):
        print i, R
        outFile.write(R+"\n")
    #for R in r_ordered[:3]:
    #    print R
    print "..."
    print 
    print "por ultimo as linhas seguintes terao 3 ou mais numeros, primeiro e o indice do nao terminal, segundo o do terminal, terceiro a da regra, correspondem a M[nt,t] = regra"
    print "nota: indice dos terminais serao de Maior_indice_dos_NT +1 ate Maior_indice_dos_NT + Maior_indice_dos_T + 1"
    print "isso pra poder botar todos simbolos em um vetor so e usar esse indice na tabela."
    deb = file("deb.txt","w")
    print "asidfa\nsdlf\nuuiu\niui"
    for NT in nt_ordered:
        for cadeia in NT_SEM_SIGMA[NT]:
            Fi = first(cadeia,0)
            Fo = Follow[NT]
            for terminal in t_ordered:
                if terminal in Fi: 
                    regra = " ".join(map(code, cadeia))
                    #M[COD_NT[NT]] [COD_T[terminal]] = COD_R[str(cadeia)]regra = " ".join(map(lamda x: str(code(x)), cadeia))
                    deb.write("NT: {2} terminal: {0}, regra: {1}\n".format(terminal, cadeia, NT))
                    outFile.write("{0} {1} {2}\n".format(COD_NT[NT], COD_T[terminal], COD_R[regra])) 
                    if NT == "<PRODUTO>":
                        print("NT: {0} , regra: {1} tud {2}".format(NT,cadeia,NT_SEM_SIGMA[NT]))
                    #print "{0} {1} {2} x1 -".format(COD_NT[NT], COD_T[terminal], COD_R[regra])
                        print "M[{0}][{1}] = {2}\n".format(NT, terminal, REGRA[COD_R[regra]])
                if SIGMA in Fi: 
                    for t in Fo:
                        regra = " ".join(map(code, cadeia))
                        #M[COD_NT[NT]] [COD_T[t]] = COD_R[str(cadeia)]regra = " ".join(map(lamda x: str(code(x)), cadeia))
                        deb.write("NT: {2} t: {0}, regra: {1}\n".format(t, cadeia, NT))
                        outFile.write("{0} {1} {2}\n".format(COD_NT[NT], COD_T[t], COD_R[regra])) 
                        if NT == "<PRODUTO>":
                            print("NT: {0} , regra: {1} tud {2}".format(NT,cadeia,NT_SEM_SIGMA[NT]))
                        #print "{0} {1} {2} x1 -".format(COD_NT[NT], COD_T[t], COD_R[regra])
                            print "M[{0}][{1}] = {2}\n".format(NT, t, REGRA[COD_R[regra]])
                
    print "Dados da tabela no arquivo: {0}".format(outFilePath)
    print first([SIGMA],0)
    deb.close()
    outFile.close()
